﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0140_SearchMatrix_II : IAlgorithm
    {
        // 搜索二维矩阵 II

        // 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
        //  每行的元素从左到右升序排列。
        //  每列的元素从上到下升序排列。

        // 提示：
        //  m == matrix.length
        //  n == matrix[i].length
        //  1 <= n, m <= 300
        //  -10^9 <= matrix[i][j] <= 10^9
        //  每行的所有元素从左到右升序排列
        //  每列的所有元素从上到下升序排列
        //  -10^9 <= target <= 10^9

        public void Test()
        {
            // 算法参数定义
            var matrix = new int[][]
            {
                new int[] { 1,4 },
                new int[] { 2,5 }
            };
            var target = 2;
            // 算法执行与打印
            Console.WriteLine(SearchMatrix(matrix, target));
        }

        // 算法
        public bool SearchMatrix(int[][] matrix, int target)
        {
            int p = 0, q = matrix[0].Length - 1;
            while (p < matrix.Length && q >= 0)
                if (matrix[p][q] > target)
                    q--;
                else if (matrix[p][q] < target)
                    p++;
                else
                    return true;
            return false;
        }
    }
}
